﻿//Given a linked list, remove the nth node from the end of list and return its head.
//For example, Given linked list : 1->2->3->4->5, and n = 2.
//After removing the second node from the end, the linked list becomes 1->2->3->5.
//Note :
//	 • Given n will always be valid.
//	 • Try to do this in one pass.

#include<iostream>
using namespace std;

template<typename T>
struct SingleList{
	T _value;
	SingleList<T> *_next;
	SingleList(T value)
		:_value(value),
		_next(NULL)
	{}
};

template<typename T>
class Solution{
public:
	SingleList<T> *Remove(SingleList<T> *head, int n)
	{
		if (head == NULL)
		{
			return head;
		}
		SingleList<T> *cur = head;
		SingleList<T> *prev = NULL;
		--n;
		while (n>=0&&cur->_next != NULL)
		{
			--n;
			prev = cur;
			cur = cur->_next;
		}
		SingleList<T> *tmp = cur;
		prev->_next = cur->_next;
		delete tmp;
		return head;
	}
	void Display(SingleList<T> *head)
	{
		if (head == NULL)
		{
			return;
		}
		SingleList<T> *cur = head;
		while (cur!=NULL)
		{
			cout << cur->_value << "->";
			cur = cur->_next;
		}
		cout << "NULL";
	}
};


int main()
{
	SingleList<int> *head = new SingleList<int>(1);
	SingleList<int> *list1 = new SingleList<int>(2);
	SingleList<int> *list2 = new SingleList<int>(3);
	SingleList<int> *list3 = new SingleList<int>(4);
	SingleList<int> *list4 = new SingleList<int>(5);
	SingleList<int> *list5 = new SingleList<int>(6);
	head->_next = list1;
	list1->_next = list2;
	list2->_next = list3;
	list3->_next = list4;
	list4->_next = list5;
	Solution<int> s;
	s.Remove(head, 2);
	s.Display(head);
}